package 动态规划;

public class climbStairs {
	
	/*
	 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

      注意：给定 n 是一个正整数。
	 */
	public static int dp(int rest) {
		//rest =0  or rest=1 dp[] 都应该为零 对吧
		int dp[] =new int [rest+1];
		 dp[0]=1;
		 dp[1]=1;
		 for(int i =2 ;i<=rest ;i++) {
			 dp[i]=dp[i-1]+dp[i-2];
		 }
		
		
		return dp[rest];
	}
	//  在  暴力 递归 中 用自然 智慧  来解决这种问题    尝试 参数 呗 尝试 
	public static int climbStairs(int rest) {
		a++;
		if(rest<0) {
			return 0;
		}
		if(rest == 0) {
			return 1;
		}
		
		return climbStairs(rest-1) +climbStairs(rest-2);
	}
	
	/*
	 * 每次你可以爬 1 或 2 个台阶,三个 台阶 、、、 直到 m个。你有多少种不同的方法可以爬到楼顶呢？

       注意：给定 n 是一个正整数。
	 */
	
	
	public static int dp(int rest,int m) {
		int dp [] =new int [rest+1];
		dp[0] = 1;
		dp[1] = 1;
			
		for(int index= 2; index<=rest;index++) {
			int ways=0;
			for(int i=1;i<=m  && index-i>=0;i++) {
				ways+=dp[index-i];
			}
			dp[index]=ways;
		}
		return  dp[rest];
		}
	public static int dp1(int rest,int m) {
		int dp [] =new int [rest+1];
		dp[0] = 1;
		dp[1] = 1;
			
		for(int index= 2; index<=rest;index++) {
			int ways=0;
			for(int i=1;i<=m  && index-i>=0;i++) {
				ways+=dp[index-i];
			}
			dp[index]=ways;
		}
		return  dp[rest];
		}
	
	
	
	
	public static int climbStairs(int rest,int m) {
		b++;
//		if(rest<0) {
//			return 0;
//		}
//		if(rest == 0) {
//			return 1;
//		}
		if(rest == 0 || rest == 1) {
			return 1;
		}
		int ways=0;
		/**
		 *   边界 条件  rest-i>=0;对吧  如果剩余 为负 还 搞个走屁啊
		 *   
		 *   
		 *   这个 rest - i>= 0 对于 这个  爬楼梯 m得 取值 只为 1 或者 2对吧 像这样 
		 *   得话
		 *   	if(rest == 0 || rest == 1) {
		    	return 1;
	     	    }
	     	    这个 basecase 就解决了 
	     	  适用于   m 比较大 的 时候 这个 才有 效果 
	     	     
		 */
		for(int i=1; i<=m && rest - i >= 0;i++) {
			ways+=climbStairs(rest-i,m);
		}
		return ways;
		//return climbStairs(rest-1) +climbStairs(rest-2);
	}
	public static int dpTwo(int n,int m) {
		int dp[] = new int [n + 1];
		dp[0] = 1;
		dp[1] =1;
		for(int i = 2; i <= n;i++) {
//			int ways = 0;
			for(int j = 1; j <=m ;j++) {
				 dp[i] +=dp[i - j];
//				 ways += dp[i - j];
			}
//			dp[i] = ways;
		}
		return dp[n];
	}
	
	
	
/**
 * 
 * 重新审视 这个 问题 
 * 重新 审视  发现  了 一些  微妙的 东西 
 * ① :   第一个 basecase 这个东西  
 * 这个  东西 真的  很微妙 啊  最关键的 递归出口的 条件 是什么 
 * 比如 这里的  楼梯 层数  n 和   m (一次 走的 楼梯书 ); m = 1,2,3,4,5 .......
 * ② : 第二个 就是          ways+= process();
 *  这个 东西 其实 理解起来  不难的 对吧  
 *  比如 二叉树的 
 *  走第一步的  那个 加号 是 可以 省略  的 
 *  理解 了 其实 看一下 就明白了
 *  		int ways = 0;
		//走一步
       //			ways += backTracing(n-1);
        * 
        * 
		ways = backTracing(n-1);
		// 走两步
		 * 
		 *  
		 *  
		ways += backTracing(n-2);
		return ways;
		或者 不写 那么 复杂   直接 一个 return climbStairs(rest-1) +climbStairs(rest-2); 结束 
		不过   这需要 一定的  熟练度 的 
		
		
		注意 递归 中 嵌套 for 循环 这种   
		int ways = 0;
		for(int i=1; i<=m && rest - i >= 0;i++) {
			ways+=climbStairs(rest-i,m);
		}
		return ways; 
 * 这个 加号  +  是不能 省掉的  
 */
public static  int backTracing(int n) {
//		if(n == 1) {
//			return 1;
//		}
//		if(n == 0) {
////			return 0;
//			return 1;
//		}
	c++;
		if(n == 0 || n == 1) {
			return 1;
		}
		int ways = 0;
		//走一步
//			ways += backTracing(n-1);
		ways = backTracing(n-1);
		// 走两步 
		ways += backTracing(n-2);
		return ways;
//		return backTracing(n-1) + backTracing(n-2);
}

/**
 * 
 * 改dp
 * 
 * 
 */
public static int dpOne(int n) {
	int dp[] = new int[n + 1];
	/**
	 * 
	 * 不要 再用     rest  (剩余)的 思想 去理解 dp数组的含义  直接 就 正着 理解 呗
	 * dp数组的 含义:  dp[i] 到达 第 i 阶楼梯 时 有 dp[i] 走法  
	 * 用 剩余的 rest 的 理解 是啥 啊
	 * dp[i] : 剩余 i 阶 楼梯 没 走 的 时候 有 dp[i] 种走法 
	 * 这 不 明显的 是 傻逼 理解嘛 
	 * 暴力递归 中 的 basecase 对应着 dp 数组的 初始化
	 * 
	 */
	dp[0] =1;
	dp[1] = 1;
	for(int i = 2; i <= n; i++) {
//		dp[i] += dp[i-1];
//		dp[i] += dp[i-2];
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

static int a;
static int b;
static int c;
public static void main(String []args) {
	// 递归的  的 次数 是一样的  这两个  说明了 啥 啊  得 根据 问题 得 认真 分析 才行 或者 思考 一下 那些 枚举行为
	//是无效的  哪些 行为 是有效  
	//①  讨论  全是 有效递归得 情况 
	//② 全部 枚举  有效递归得 情况  坑定全部 包括 在内  但是  递归 次数 变多了   
	// 而 这个 爬楼梯 这个 全部 可能得 递归 与 有效 递归 是一样 得  所以这种情况下 两者 递归得次数情况一样
	System.out.println(climbStairs(10));
	System.out.println(climbStairs(10,2));
//	System.out.println(dp(10,4));
	System.out.println(backTracing(10));
	System.out.println(a + " " + b + " " + c);
	System.out.println(dpOne(10));
	System.out.println(dpTwo(10,2));
}
	
}
